{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bisection in Two Dimensions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We describe basic idea of the newest vertex and the longest edge bisection\n",
    "algorithm for two dimensional triangular grids. In short, a bisection refinement will divide one triangle into two children triangles by connecting one vertex to the middle point of its opposite edge. Another class of mesh refinement method, known as regular refinement, which divide one triangle into 4 similar small triangles, is implemented in `uniformrefine.m`.\n",
    "\n",
    "There are two main issues in designing a good bisection method.\n",
    "\n",
    "- (B1) Shape regularity.\n",
    "- (B2) Conformity. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Newest vertex bisection\n",
    "\n",
    "If keep cutting one edge, the smallest angle will decrease and approach\n",
    "to zero. To keep the shape regularity, we can switch the edge to be\n",
    "cutted. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Newest vertex bisection\n",
    "Newest vertex bisection is to assign the refinement edge as the\n",
    "edge opposite to the newest vertex added in the bisection. To begin with,\n",
    "for an initial triangulation $\\mathcal T_0$, we can label the longest edge of each triangle as the refinement edge. Once a initial labeling is assigned to $\\mathcal T_0$, \n",
    "the refinement edges of all descendants of triangles in $\\mathcal T_0$ is\n",
    "determined by the combinatorial structure of the triangulation. \n",
    "\n",
    "It can be shown that all the descendants of a triangle in $\\mathcal T_0$ \n",
    "fall into four similarity classes and hence (B1) holds. See the following\n",
    "figure for an illustration\n",
    "\n",
    "<img src=\"./figures/similarclass.png\" width=\"120%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Refinement edge\n",
    "How to represent a labeled triangulation? Recall that our representation\n",
    "of a triangle: `elem(t,[1 2 3])` are global indices of three vertices of\n",
    "the triangle `t`. The only requirement on the ordering is that the\n",
    "orientation is counter-clockwise. A cyclical permutation of three indices\n",
    "still represents the same triangle. We make use of this room and use the rule:\n",
    "\n",
    "> The refinement edge of `t` is `elem(t,[2 3])`.\n",
    "\n",
    "In other wordes, for the newest vertex bisection, `elem(t,1)` will be always the newest vertex of the triangle `t`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Completion\n",
    "\n",
    "Bisect some traingles in a triangulation could result in hanging nodes.\n",
    "Neighboring triangles should be bisected (again following the newest\n",
    "vertex rule) to eliminate hangning nodes. This procedure is called\n",
    "completion.\n",
    "\n",
    "<img src=\"./figures/completion.png\" width=\"75%\">\n",
    "\n",
    "We now describe an efficient completion algorithm for 2-D triangulations.\n",
    "A key observation is that if we cut all edges of the current\n",
    "triangulation (by the newest vertex bisection rule), it results in a\n",
    "conforming triangulation. Therefore instead of operating on triangles,\n",
    "we cut enough edges to ensure the conformity. \n",
    "\n",
    "Let us denote the refinement edge of `t` by `cutEdge(t)`. We define the\n",
    "refinement neighbor of `t`, denoted by `refineNeighbor(t)`, as the\n",
    "neighbor sharing the refinement edge of `t`. When `cutEdge(t)` is on the\n",
    "boundary, we define `refineNeighbor(t) = t`. Note that `cutEdge(t)` may\n",
    "not be the refinement edge of `refineNeighbor(t)`. To ensure the\n",
    "conformity, it suffices to satisfy the rule \n",
    "\n",
    ">If `cutEdge(t)` is marked for bisection, so is `cutEdge(refineNeighbor(t))`.\n",
    "\n",
    "See `bisect.m` adding new nodes section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "%% Add new nodes\n",
    "isCutEdge = false(NE,1);\n",
    "while sum(markedElem)>0\n",
    "    isCutEdge(elem2edge(markedElem,1)) = true;\n",
    "    refineNeighbor = neighbor(markedElem,1);\n",
    "    markedElem = refineNeighbor(~isCutEdge(elem2edge(refineNeighbor,1)));\n",
    "end\n",
    "edge2newNode = zeros(NE,1,'uint32');\n",
    "edge2newNode(isCutEdge) = N+1:N+sum(isCutEdge);\n",
    "node(edge2newNode(isCutEdge),:) = (node(edge(isCutEdge,1),:) + ...\n",
    "                                   node(edge(isCutEdge,2),:))/2;\n",
    "                                   ```                                  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bisections of marked triangles\n",
    "We only need to bisect the triangle whose refinement edge is bisected.\n",
    "The local numbering is shown in the following figure. We only need to bisect the triangle whose refinement edge is bisected. The local numbering is shown in the following figure. Note that we repeat the bisection only twice. No loop over all triangles. We also need to\n",
    "update the boundary condition i.e. `bdFlag`. \n",
    "\n",
    "<img src=\"./figures/bisectrefinement.pdf\" width=\"85%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "%% Refine marked elements\n",
    "Nb = 0; tree = zeros(3*NT,3,'uint32');\n",
    "for k = 1:2\n",
    "    t = find(edge2newNode(elem2edge(:,1))>0);\n",
    "    newNT = length(t);\n",
    "    if (newNT == 0), break; end\n",
    "    L = t; R = NT+1:NT+newNT;\n",
    "    p1 = elem(t,1); p2 = elem(t,2); p3 = elem(t,3);\n",
    "    p4 = edge2newNode(elem2edge(t,1));\n",
    "    elem(L,:) = [p4, p1, p2];\n",
    "    elem(R,:) = [p4, p3, p1];\n",
    "    elem2edge(L,1) = elem2edge(t,3);\n",
    "    elem2edge(R,1) = elem2edge(t,2);\n",
    "    NT = NT + newNT; Nb = Nb + newNT;\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initial labeling\n",
    "\n",
    "Although the completion procedure we proposed will terminate for\n",
    "arbitrary initial labeling, for the sake of shape regularity, we assign\n",
    "the longest edge as the refinement edge of each triangle in the initial\n",
    "triangulation. The subroutine `elem = label(node,elem)` will permute the vertices such that `elem(t,2:3)` is the longest edge of `t`. Note that it  is only need for the initial triangulation. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Longest Edge Bisection\n",
    "It is interesting to note that if we call `label` before each call of\n",
    "`bisect`, then `bisect` becomes the longest edge bisection since\n",
    "everytime we switch the refinement edge to the longest edge.\n",
    "\n",
    "The longest edge bisection will produce shape regular triangulations.\n",
    "Intuitively the longest edge bisection divides the largest angle, which\n",
    "in turn prevent forming small angles. Rosenberg and Stenger proved that\n",
    "by always bisecting the longest edge, the smallest angle possible is half\n",
    "of the smallest angle in the initial triangulation."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Matlab",
   "language": "matlab",
   "name": "matlab"
  },
  "language_info": {
   "codemirror_mode": "octave",
   "file_extension": ".m",
   "help_links": [
    {
     "text": "MetaKernel Magics",
     "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md"
    }
   ],
   "mimetype": "text/x-matlab",
   "name": "matlab",
   "version": "0.14.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "156px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": true,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
